Networks contain a collection of computing systems (e.g., clients and servers) that are interconnected by transmission lines to enable the transfer of data between them. A network typically includes multiple access points (e.g., routers and servers) that may switch and/or route data between transmission lines to transfer data from a source to a destination. Data is typically transmitted in the form of packets that are made up of smaller data cells. A packet is a unit of data that is routed between a source and a destination on a packet-switched network. When a file (e.g., e-mail, graphics, etc.) is sent from one place to another on a network, the file is divided into such smaller packets making them more efficient for transmission. The individual packets for a given file may travel different routes throughout networks with each packet containing both data and transmission information associated with the routing of data. As such, a packet may be described as having a payload containing the data, and one or more headers that contain the routing information (e.g., a destination address).
When all the packets have arrived at a destination, they are reassembled into the original file at the receiving end. Such a packet switching scheme is an efficient way to handle transmission on a connectionless network. This is in contrast to a circuit switching scheme where a connection (e.g., a voice connection) requires the dedication of a particular path for the duration of the connection.
A router is a device (e.g., hardware, firmware, software) that determines the next network segment to which a packet should be forwarded towards its destination. A router may be positioned at points within a network or where one network meets another, referred to as a gateway. A router may create and maintain tables of the available routes and their conditions (routing tables) for use with other information to determine the best route for a given packet. Typically, a packet may travel through a number of network points having routers before arriving at its destination.
When a data packet arrives at the input of a router, several lookups may be performed by the router to determine the subsequent handling of the packet, as illustrated in FIG. 1. The lookups may include, for examples, where to send the packet next (Next Hop), the quality of service requirement (QoS), the Ethernet port address, etc. Consider, for example, a packet arriving at Router-A. Router-A needs to determine whether the packet is destined for local servers connected directly to Router-A, or if the packet should go to the next router on a route (Router-B) to a destination. Additionally, Router-A may assign a priority based on the destination address (DA) and the source address (SA) of the packet.
The packet header may first be parsed or processed to get the values from different fields (e.g., SA, DA, protocol type, QoS, etc) in order to perform the various lookups. A packet classification lookup, for example, may be performed using SA, DA and other relevant fields in the packet header. The Next Hop lookup, for example, may also be performed to determine whether the packet is meant for local servers or for Router-B. If the packet is destined for Router-B, the packet is then put in a queue for Router-B. If the packet is destined for a local server (e.g., Server-1 or Server-2), then a media access control (MAC) lookup is performed to send the packet to the appropriate server. In the preceding example, three lookups are necessary for sending the packet on its way: Packet Classification, Next Hop, and MAC. However, often there are other lookups performed on the packet header, with the number of lookups exceeding five or more.
Routers may use processors (e.g., network processor, control plane processor, microprocessor, etc.) and content addressable memory (CAM) devices to perform the various lookups on packets. The CAM device can be instructed by the processor to compare a search key, also referred to as a comparand (e.g., generated from packet header data), with data stored in its associative memory array. The CAM simultaneously examines all of its entries and selects the stored data that matches the key. As such, before a search can be performed, data must be stored in the CAM array.
When the entire CAM device is searched simultaneously for a match of the stored data with the key comparand data, the CAM device indicates the existence of a match by asserting a match flag using match flag logic, as illustrated in FIG. 2. Multiple matches may also be indicated by asserting a multiple match flag. The CAM device typically includes a priority encoder to translate the matched location into a match address or CAM index and outputs this address to a status register so that the matched data may be accessed. The priority encoder may also sort out which matching memory location has the top priority if there is more than one matching entry.
Data may be represented in the form of strings of binary digits (“bits”) having a low (“0”) logic state and a high (“1”) logic state. Different types of CAM devices may be used with different data formats. A binary CAM is designed to operate with “0” and “1” states, while a ternary CAM is designed to operate with “0”, “1”, and “don't care” states. The bits may be organized into groups such as a word (e.g., 64 or 72 bits wide) and stored in different segments of a CAM device. The search keys used for different data fields may have different word sizes, for example, the search key for a Classification lookup may be 128 bits wide and the search key for a Next Hop lookup may be 32 bits wide.
A CAM device may include multiple blocks with each block storing a different table, for performing a different lookup. For example, a router may include a 32 bit wide Next Hop CAM block, a 128 bit Classification CAM block, and a 48 bit MAC CAM block. Each of the multiple CAM blocks within a CAM device are typically connected to common data and instruction buses that are used to communicate the various keys and other input and output data with the processor. The search key is usually provided together with instructions to the CAM device on the instruction bus. The instructions typically contain information about the blocks contained within the CAM device, for example, block or table identifiers and global masking identifiers associated with a particular search.
Some prior art CAM devices utilize large instruction bus widths in order to receive such information. For example, if 2 bits are used to designate a block ID and 3 bits are used to designate global masking ID, then an instruction bus would need to be at least 5 bits. If multiple, concurrent searches were supported, and each compare operation could identify a unique table identifier/global mask combination, the width of the instruction bus may be undesirably increased to simultaneously accommodate all of the compare instructions. As the number of lookups increases, such CAM device architectures could undesirably limit the system's overall throughput.